package com.gaofeng.algo.kt

fun searchRange(numbs: IntArray, target: Int): IntArray? {
    if (numbs.isEmpty()) {
        return intArrayOf(-1, -1)
    }
    val lower = lowerBound(numbs, target)
    val upper = upperBound(numbs, target) - 1
    return if (lower == numbs.size || numbs[lower] != target) {
        intArrayOf(-1, -1)
    } else intArrayOf(lower, upper)
}

private fun lowerBound(numbers: IntArray, target: Int): Int {
    var lo = 0
    var hi = numbers.size
    var mid: Int
    while (lo < hi) {
        mid = lo + (hi - lo) / 2
        if (numbers[mid] >= target) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

private fun upperBound(numbers: IntArray, target: Int): Int {
    var lo = 0
    var hi = numbers.size
    var mid: Int
    while (lo < hi) {
        mid = lo + (hi - lo) / 2
        if (numbers[mid] > target) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}


fun search(numbers: IntArray, target: Int): Boolean {
    var lo = 0
    var hi = numbers.size - 1
    var mid: Int
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2
        if (numbers[mid] == target) {
            return true
        }
        if (numbers[mid] == numbers[lo]) {
            lo++
        } else if (numbers[mid] <= numbers[hi]) {
            if (target > numbers[mid] && target <= numbers[hi]) {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        } else {
            if (target < numbers[mid] && target >= numbers[lo]) {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        }
    }
    return false
}
